A stream cipher is a system for encryption and decryption of digital data.
Reference is now made to FIG. 1, which is a stream cipher 10. The stream cipher 10 usually employs a pseudo-random number generator 12 (PRNG) in the following way. The pseudo-random number generator 12 is typically fed with a key 14 (K) and an initial value 16 (IV) and generally derives there from a keystream 18 (KS) of arbitrary length. The encryption of a plaintext 20 is typically the result of an exclusive-OR (XOR) operation, performed by a combiner 21, on the plaintext 20 and a corresponding prefix of the keystream 18 thus providing ciphertext 22. Similarly, the decryption of the ciphertext 22 is typically the result of an XOR operation when performed on the ciphertext 22 and a corresponding prefix of the keystream 18 thus providing the plaintext 20. The combiner 21 has been described herein as an XOR combiner. However, it will be appreciated by those ordinarily skilled in the art that other suitable combiners can be used, for example, but not limited to, an additive combiner.
Reference is now made to FIG. 2, which is a detailed view of pseudo-random number generator 12 of the stream cipher 10 of FIG. 1. Many stream ciphers are based on a secret internal state 30 and on three modules. The three modules typically include an initialization module 24, a state update module 26 and an output word module 28. The initialization module 24 is typically used at initialization for translating the IV 16 and the key 14 into an initial state. Then, the cipher 10 generally enters a loop where the state update module 26 updates the state 30 and the output word module 28 uses the updated state 30 to output a next word of the keystream 18. The cipher 10 preferably continues performing the loop until a sufficiently long keystream 18 is emitted.
The output word is typically a bit (as in LFSR-based stream ciphers), a byte (as in RC4), or a block of any length. Stream ciphers are also known as state ciphers, since they usually maintain an internal state.
In some cases the initialization module 24 takes as input only the key 14 (K), whereas in other cases the initialization module 24 takes as input the key 14 (K) and the IV 16.
Some known stream ciphers are:
“RC4”, described in more detail in “Analysis methods for (Alleged) RC4” by Lars R. Knudsen, Willi Meier, Bart Preneel, Vincent Rijmen and Sven Verdoolaege of the Department of Informatics, University of Bergen, Bergen also available at www.cosic.esat.kuleuven.be/publications/article-68.pdf;
“RC4A”, described in more detail in “A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher,” in Fast Software Encryption, FSE 2004, Lecture Notes in Computer Science 3017, Bimal Roy, Willi Meier (Eds.), Springer-Verlag, 2004, pp. 245-259, available via www.esat.kuleuven.be/˜psourady/papers.html;
“VMPC”, described in more detail in “VMPC One-Way Function and Stream Cipher” by Bartosz Zoltak presented at FSE '04, Delhi, India, 5-7 Feb. 2004, available at www.vmpcfunction.com/vmpc.pdf;
“SEAL”, described in more detail in “Handbook of Applied Cryptography” by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, published by CRC Press; and
“A5/1”, described in more detail in “Real Time Cryptanalysis of A5/1 on a PC” by Alex Biryukov, Adi Shamir and David Wagner presented at the FSE Workshop 2000, Apr. 10-12, 2000, New York, N.Y. USA, available at cryptome.org/a51-bsw.htm.
A table-shuffle stream cipher is a stream cipher generally having a certain structure of the state 30 and the state update module 26. In a table-shuffle stream cipher, the pseudo-random number generator 12 preferably maintains the state 30 including a stream cipher table of size N. The contents of the table are typically numbered between zero and N−1, permuted in some order. The main part of the secrecy of the state resides in the permutation. In addition, the table generally comprises a set of indices for the table, namely numbers between 0 and N−1 inclusive. The indices are typically divided into traversal indices and pseudo-random indices, differing in the way they are updated by the state update module 26.
The state update module 26 of a table-shuffle stream) cipher preferably updates pseudo-random indices in a way that depends on the order of the values in the table, and updates traversal indices in a way that is independent of the order of the values in the table when the update takes place. The values in the table entries that are pointed to by the indices are referred to as the “refresh set”. The state update module 26 preferably updates the table by permuting the values in the refresh set, namely values in the refresh set may change places with other values in the refresh set.
The state 30 of a table-shuffle stream cipher may comprise several tables with equal or different sizes. In that case, every index typically points to one or more tables and the refresh set can include values from several tables. In most of the cases the state update module 26 generally only moves values inside the tables, but does not move values between the tables.
The following is an example according to the RC4 stream cipher system, which operates with one table of 256 entries, one traversal index, i, and one pseudo-random index, j. To generate an output word, the following is preferably performed.
First, a state update is preferably performed by performing the following two updates:i=(i+1)mod 256  (Equation 1), andj=(j+S[i])mod 256  (Equation 2),
where S[x] is the value in the xth location of the table.
S[i] and S[j] are the refresh set of the state update module 26,
Then S[i] and S[j] are typically swapped with each other.
Therefore, the state update generally takes an input state and provides a (usually slightly) different output state.
Next, the output word module 28 preferably performs the following on the state 30:t=(S[i]+S[j])mod 256  (Equation 3),
determine S[t] as the output word.
In other words the calculation of the output word can be represented by:S[(S[i]+S[j])] mod 256]  (Equation 4).
Table-shuffle stream ciphers (including RC4) are described in more detail with reference to Applied Cryptography by Bruce Schneier, published by John Wiley & Sons, Inc. in 1996 page 397-398.
Patents in the related art include U.S. Pat. No. 6,785,389 to Sella, et al.
The disclosures of all references mentioned above and throughout the present specification, as well as the disclosures of all references mentioned in those references, are hereby incorporated herein by reference.